package com.utils;

class Test {

    public void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }

        int l = left;
        int r = right;

        int temp = arr[left];

        while (left < right) {
            while (left < right && arr[right] >= temp) {
                right--;
            }

            while (left < right && arr[left] <= temp) {
                left++;
            }

            swapArr(arr, left, right);
        }

        swapArr(arr, l, left);

        quickSort(arr, l, left - 1);
        quickSort(arr, right + 1, r);

    }

    private void swapArr(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {
//        int[] arr = new int[]{4, 3};
        int[] arr = new int[]{4, 3, 12, 4, 0, 18, 9};
//        int[] arr = new int[]{1,2,3,4,5,7,6};
//        int[] arr = new int[]{4, 3, 12};

        Test test = new Test();
        test.quickSort(arr, 0, arr.length - 1);

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

}
